/*
 * @lc app=leetcode.cn id=1575 lang=cpp
 *
 * [1575] 统计所有可行路径
 *
 * https://leetcode.cn/problems/count-all-possible-routes/description/
 *
 * algorithms
 * Hard (56.36%)
 * Likes:    117
 * Dislikes: 0
 * Total Accepted:    14.3K
 * Total Submissions: 25.4K
 * Testcase Example:  '[2,3,6,8,4]\n1\n3\n5'
 *
 * 给你一个 互不相同 的整数数组，其中 locations[i] 表示第 i 个城市的位置。同时给你 start，finish 和 fuel
 * 分别表示出发城市、目的地城市和你初始拥有的汽油总量
 *
 * 每一步中，如果你在城市 i ，你可以选择任意一个城市 j ，满足  j != i 且 0 <= j < locations.length ，并移动到城市
 * j 。从城市 i 移动到 j 消耗的汽油量为 |locations[i] - locations[j]|，|x| 表示 x 的绝对值。
 *
 * 请注意， fuel 任何时刻都 不能 为负，且你 可以 经过任意城市超过一次（包括 start 和 finish ）。
 *
 * 请你返回从 start 到 finish 所有可能路径的数目。
 *
 * 由于答案可能很大， 请将它对 10^9 + 7 取余后返回。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5
 * 输出：4
 * 解释：以下为所有可能路径，每一条都用了 5 单位的汽油：
 * 1 -> 3
 * 1 -> 2 -> 3
 * 1 -> 4 -> 3
 * 1 -> 4 -> 2 -> 3
 *
 *
 * 示例 2：
 *
 *
 * 输入：locations = [4,3,1], start = 1, finish = 0, fuel = 6
 * 输出：5
 * 解释：以下为所有可能的路径：
 * 1 -> 0，使用汽油量为 fuel = 1
 * 1 -> 2 -> 0，使用汽油量为 fuel = 5
 * 1 -> 2 -> 1 -> 0，使用汽油量为 fuel = 5
 * 1 -> 0 -> 1 -> 0，使用汽油量为 fuel = 3
 * 1 -> 0 -> 1 -> 0 -> 1 -> 0，使用汽油量为 fuel = 5
 *
 *
 * 示例 3：
 *
 *
 * 输入：locations = [5,2,1], start = 0, finish = 2, fuel = 3
 * 输出：0
 * 解释：没有办法只用 3 单位的汽油从 0 到达 2 。因为最短路径需要 4 单位的汽油。
 *
 *
 *
 * 提示：
 *
 *
 * 2 <= locations.length <= 100
 * 1 <= locations[i] <= 10^9
 * 所有 locations 中的整数 互不相同 。
 * 0 <= start, finish < locations.length
 * 1 <= fuel <= 200
 *
 *
 */
#include <bits/stdc++.h>
using namespace std;
// @lc code=start
#define MOD 1000000007
class Solution {
public:
    int countRoutes(vector<int>& locations, int start, int finish, int fuel) {
        vector<vector<int>> memo(locations.size(), vector<int>(fuel + 1, -1));
        return bactTrace(locations, start, finish, fuel, memo);
    }
    int bactTrace(vector<int>& locations, int cur, int finish, int fuel, vector<vector<int>>& memo) {
        // 从当前位置一步走不到finish, 多步必定走不到
        if (fuel < 0 || fuel < abs(locations[cur] - locations[finish])) return 0;

        if (memo[cur][fuel] >= 0) {
            return memo[cur][fuel];
        }
        int res = cur == finish ? 1 : 0;
        for (int i = 0; i < locations.size(); i++) {
            int cost = abs(locations[cur] - locations[i]);
            if (i == cur) continue;
            res = (res + bactTrace(locations, i, finish, fuel - cost, memo)) % MOD;
        }
        memo[cur][fuel] = res;
        return res;
    }
};
// @lc code=end

// int main(int argc, char const* argv[]) {
//     Solution s = Solution();
//     vector<int> in = {1, 2, 3};
//     int res = s.countRoutes(in, 0, 2, 40);
//     cout << "res = " << res << endl;
//     return 0;
// }
